"""
一个使用动态规划（基于BFS的变种）的路径规划器。
它被设计用来在网格迷宫中，寻找一条终点必须是EXIT、不包含回路（不重复访问格子）的、
可以获得最短的路径。

暂时没有启用
"""

from collections import deque
from config import *
from typing import Tuple, List, Dict
import numpy as np

class DPPlannerBFS:
    def __init__(self, maze_grid):
        """
        初始化规划器。
        :param maze_grid: 代表迷宫的Numpy数组。
        """
        self.maze = maze_grid
        self.rows, self.cols = maze_grid.shape

        # 基础分值表
        self.base_value_map = {
            GOLD: 5, TRAP: -3, PATH: 0, START: 0,
            BOSS: 15, LOCKER: 10,
            EXIT: 0  # 终点奖励分将单独计算
        }
        self.exit_bonus = 10

    def _get_strategic_value_map(self, mode: str) -> Dict[str, float]:
        """
        根据不同的策略模式，生成对应的分值表。
        """
        value_map = self.base_value_map.copy()
        if mode == 'safe_gold':
            value_map[BOSS] = 0
            value_map[LOCKER] = 0
        elif mode != 'full_quest':
            raise ValueError("无效的模式。请选择 'full_quest' 或 'safe_gold'。")
        return value_map

    def calculate_optimal_path(self, mode: str = 'full_quest') -> Tuple[List[Tuple[int, int]], float]:
        """
        使用基于广度优先搜索的动态规划，计算终点为EXIT的无回路最高分路径。
        """
        value_map = self._get_strategic_value_map(mode)
        start_pos = None
        for r in range(self.rows):
            for c in range(self.cols):
                if self.maze[r, c] == START:
                    start_pos = (r, c)
                    break
            if start_pos:
                break

        if not start_pos:
            return [], 0

        dp_scores = np.full((self.rows, self.cols), -float('inf'), dtype=float)
        predecessors = {}

        # 队列中的每个元素是 (坐标, 当前路径得分, 当前路径集合)
        queue = deque([(start_pos, value_map.get(self.maze[start_pos], 0), {start_pos})])
        dp_scores[start_pos] = value_map.get(self.maze[start_pos], 0)
        predecessors[start_pos] = None

        while queue:
            (r, c), current_score, visited_path = queue.popleft()

            for dr in [-1, 0, 1]:
                for dc in [-1, 0, 1]:
                    if dr == 0 and dc == 0: continue

                    nr, nc = r + dr, c + dc

                    if not (0 <= nr < self.rows and 0 <= nc < self.cols and self.maze[nr, nc] != WALL):
                        continue

                    neighbor = (nr, nc)
                    if neighbor in visited_path: continue

                    new_score = current_score + value_map.get(self.maze[neighbor], 0)
                    if new_score > dp_scores[neighbor]:
                        dp_scores[neighbor] = new_score
                        predecessors[neighbor] = (r, c)
                        new_visited_path = visited_path.copy()
                        new_visited_path.add(neighbor)
                        queue.append((neighbor, new_score, new_visited_path))

        # 只在所有可达的EXIT中寻找最优终点
        best_target_pos = None
        max_total_score = -float('inf')

        # 遍历所有格子，但只对EXIT格子进行最终评分比较
        for r in range(self.rows):
            for c in range(self.cols):
                # 必须是EXIT格子，并且是从起点可达的
                if self.maze[r, c] == EXIT and dp_scores[r, c] > -float('inf'):
                    cell = (r, c)
                    # 路径得分是从DP表中获得
                    path_score = dp_scores[cell]

                    # 总分 = 路径得分 + 终点额外奖励分
                    total_score = path_score + self.exit_bonus

                    # 如果这个EXIT的总分更高，则更新为最优目标
                    if total_score > max_total_score:
                        max_total_score = total_score
                        best_target_pos = cell

        # 如果没有任何一个EXIT是可达的
        if not best_target_pos:
            return [], 0

        # 从找到的最优EXIT回溯路径
        path = []
        curr = best_target_pos
        while curr is not None:
            path.append(curr)
            curr = predecessors.get(curr)
        path.reverse()

        return path, max_total_score
